import { Sort } from "../public/Sort"
import { DefaultCompare, ICompareFunction, CompareEnum } from "../public/Utils"
/**
 * 基数排序
 * 基数排序也是一个分布式排序算法，它根据数字的有效位或基数将整数分布到桶中。
 * 比如，十进制数，使用的基数是10。
 * 因此，算法将会使用10个桶用来分布元素并且首先基于各位数字进行排序，
 * 然后基于十位数字，然后基于百位数字，以此类推。
 * 基数排序是使用空间换时间的经典算法
 * **/
export class RadixSort<T> extends Sort<T> {
    constructor(array: Array<T> = [], compareFun: ICompareFunction = new DefaultCompare()) {
        super(array, compareFun)
    }
    sort(array: Array<T> = this.array, n: number = 0): Array<T> {
        //定义一个二维数组，表示十个桶，每个桶就是一个一维数组
        //说明：
        //1.二维数组包含10个一维数组
        //2.为了防止在放入数组的时候数据溢出，则每个一维数组（桶）大小限定为n
        let bucket: Array<Array<T>> = new Array<Array<T>>(10)
        for (let i: number = 0; i < bucket.length; i++) {
            bucket[i] = new Array(n);
        }
        //为了记录每个桶中，实际存了多少个数据，定义一个一维数组来记录
        //每个桶的每次放入的数据个数
        //如：bucketElementCounts = new Array(10).fill(0)
        let bucketElementCounts = new Array(10).fill(0)
        let maxValue = array.reduce((a, b) => {
            return a > b ? a : b
        })
        let maxLength: number = (maxValue + '').length
        for (let i = 0, n = 1; i < maxLength; i++, n = n * 10) {
            //每一轮，对每个元素的各个位数进行排序处理
            //第一次是个位，第二次是十位，第三次是百位
            for (let j = 0; j < n; j++) {
                //取出各个元素各位置的值
                let elementValue = Math.floor(<number>array[j] / n) % 10
                if (!Number.isNaN(elementValue)) {
                    bucket[elementValue][bucketElementCounts[elementValue]] = array[j] 
                }
                bucketElementCounts[elementValue]++
            }

            //按照这个桶的顺序（以数组的下标依次取出数据，放入原数组）
            let index: number = 0
            //遍历每一个桶，并将桶中的数据放入原数据
            for (let i = 0; i < bucketElementCounts.length; i++) {
                //如果桶中有数据，我们才放入原数组
                if (bucketElementCounts[i] !== 0) {
                    for (let l = 0; l < bucketElementCounts[i]; l++) {
                        const element = array[l];
                        array[index] = bucket[i][l]
                        index++
                    }
                    //重置下标
                    bucketElementCounts[i] = 0;
                }

            }
        }
        return array
    }
}

const RadixSortTest = (): void => {
    const array = [33, 67.3, 15.66, 54, 88,3,5,5]
    const bucketSort: Sort<Number> = new RadixSort<Number>(array)
    console.log(bucketSort.sort());
}
RadixSortTest()